package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         23,
		Discription: "合并k个升序链表",
		Level:       3,
		Labels: map[string]int{
			"链表":    1,
			"大小堆":   1,
			"虚拟头指针": 1,
		},
	})
}

func MergeKLists(lists []*ds.ListNode) *ds.ListNode {
	s := make([]*ds.ListNode, 0)
	insert := func(node *ds.ListNode) {
		s = append(s, node)
		i := len(s) - 1
		for (i-1)/2 >= 0 {
			parentIndex := (i - 1) / 2
			if s[parentIndex].Val <= node.Val {
				break
			}

			s[i], s[parentIndex] = s[parentIndex], s[i]
			i = parentIndex
		}
	}

	pop := func() *ds.ListNode {
		res := s[0]
		if len(s) == 1 {
			s = make([]*ds.ListNode, 0)
			return res
		}

		s[0], s[len(s)-1] = s[len(s)-1], s[0]
		s = s[:len(s)-1]
		i := 0
		topVal := s[0].Val
		n := len(s) - 1
		for 2*i+1 <= n {
			leftIndex := 2*i + 1
			rightIndex := leftIndex + 1
			smallerIndex := leftIndex
			if rightIndex <= n && s[rightIndex].Val < s[leftIndex].Val {
				smallerIndex = rightIndex
			}

			if topVal <= s[smallerIndex].Val {
				break
			}

			s[i], s[smallerIndex] = s[smallerIndex], s[i]
			i = smallerIndex
		}

		return res
	}

	for _, node := range lists {
		if node != nil {
			insert(node)
		}
	}

	preHead := &ds.ListNode{}
	cur := preHead
	for len(s) != 0 {
		smallestNode := pop()
		cur.Next = smallestNode
		cur = cur.Next
		if smallestNode.Next != nil {
			insert(smallestNode.Next)
		}
	}

	return preHead.Next
}

/* func MergeKLists(lists []*ds.ListNode) *ds.ListNode {
	h := make([]*ds.ListNode, 0)
	for _, node := range lists {
		if node != nil {
			h = append(h, node)
		}
	}
	smallHeap := &ds.SmallHeap{
		Lists: h,
	}
	smallHeap.Init()

	preHead := &ds.ListNode{}
	temp := preHead
	for !smallHeap.IsEmpty() {
		smallestNode := smallHeap.PopHeap()
		temp.Next = smallestNode
		temp = temp.Next
		if smallestNode.Next != nil {
			smallHeap.PushHeap(smallestNode.Next)
		}
	}

	return preHead.Next
}
 */